Aim

This script shows how to estimate spillover from single metal spots on an agarose coated slide. Each spot should be imaged with a single acquisition. The name of the acquisition should be the metal that is used: E.g. PanormaA_1_Yb176_23.txt

When run with the example data it reproduces the spillover estimation shown in Fig S5A as well as Fig 4A

Script

load all libraries

library(CATALYST)
package ‘CATALYST’ was built under R version 3.4.3
library(data.table)
library(ggplot2)
library(flowCore)
library(dplyr)
library(dtplyr)
library(stringr)
source('spillover_imc_helpers.R')

setup the configuration variables

# list of folders that contain each a complete single stain acquisition (e.g. in case that one wants to run and compare multiple single stains from different days)
fols_ss = c('../data/Figure_S5/Spillover_Matrix_2','../data/Figure_S5/Spillover_Matrix_1' )
# output folder
fol_out = '../data/Figure_S5/'
# name prefix for all output
prefix = paste0(Sys.Date(), '_v1_')

load single stains

Data loading

# load the data
list_img_ss <-lapply(fols_ss, load_ss_fol)
names(list_img_ss) <- fols_ss

Adapt the column names to be recognized metal names by CATALYST

CATALYST needs to have the metal names in the format (METAL)(MASS)Di

list_img_ss = lapply(list_img_ss, function(x) lapply(x, fixnames))
dats_raw = lapply(list_img_ss, imglist2dat)

Extract the single stain masses from the acquisition name

This needs to be changed in case a different naming scheme is used!

for (dat in dats_raw){
  dat[, metal:= strsplit(.BY[[1]], '_')[[1]][3],by=file]
  dat[, mass:= as.numeric(str_extract_all(.BY[[1]], "[0-9]+")[[1]]),by=metal]
}

Visualization of the raw data

In the following section the raw data is visualized

Calculate per-file medians

dats_raw_sum = rbindlist(lapply(dats_raw, calc_file_medians),idcol = T)

Visualize per-file medians

Plots the median of the data. It is recommended to have >200 counts for all the channels. This is also a good plot to check if the metal spots really contain the correct metal!

dats_raw_sum %>%
  ggplot(aes(x=mass, y=med, color=.id))+
  facet_wrap(~file+metal, scales = 'free_y')+
  geom_label(aes(label=variable), size=4)

Optional data bining

If the median per-pixel intensities are to low, it could be worth to sum up some consecuteive pixels to get a better accuracy for the estimation (here not the case). This is valid because for segmentation based quantitative image analysis usually anyways pixels are aggregated. If the binning is choosen to big, there is however a potential accumulation of background noise.

# defines over how many pixels the aggregation should happen
# 1 = no aggregation
npixelbin = 1
dats_agg <- lapply(dats_raw, function(x) aggregate_pixels(x, n=npixelbin))
dats_agg_sum = rbindlist(lapply(dats_agg, calc_file_medians), idcol = T)

Visualize per-file medians after binning

The intensities increase according to the aggregation factor

dats_agg_sum %>%
  ggplot(aes(x=mass, y=med, color=.id))+
  facet_wrap(~file+metal, scales = 'free_y')+
  geom_label(aes(label=variable))

CATALYST based compensation

Definition of some helper functions

estimate the spillover

To estimate the spillover, the (aggregated) pixel values are first debarcoded using CATALYST, treating them like single cells. This step acts as a quality filter to remove background/noisy/weak pixels as well as pixels with artefacts (e.g. specles with strong signal in many channels). If the true metal was correctly encoded in the filename, the ‘remove_incorrect_bc’ option will check the debarcoding and remove events assigned to the wrong barcode.

Then this identified, strong single stain pixels will be used for the spillover estimation.

res = lapply(dats_agg, function(x) re_from_dat(x,
                                               ss_ms=x[!is.na(mass), unique(mass)],
                                               minevents = 40,
                                              correct_bc = x[ , unique(mass)]))
Debarcoding data...
 o ordering
 o classifying events
Normalizing...
Computing deltas...
Computing counts and yields...
NaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedDebarcoding data...
 o ordering
 o classifying events
Normalizing...
Computing deltas...
Computing counts and yields...
NaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs produced
sms = lapply(res, function(x) computeSpillmat(x))

save the spillover matrices

for (i in seq_along(sms)){
  outname = file.path(fol_out, paste0(prefix, basename(fols_ss[i]),'_sm.csv'))
  write.csv(sms[[i]],file = outname)
}

Visualization of the spillover matrix

for (i in seq_along(sms)){
  print(names(dats_agg)[i])
  ss_ms = dats_agg[[i]][!is.na(mass), unique(mass)]
  p = CATALYST::plotSpillmat(ss_ms,sms[[i]])
  print(p)
}
[1] "../data/Figure_S5/Spillover_Matrix_2"
We recommend that you use the dev version of ggplot2 with `ggplotly()`
Install it with: `devtools::install_github('hadley/ggplot2')`

[1] "../data/Figure_S5/Spillover_Matrix_1"
We recommend that you use the dev version of ggplot2 with `ggplotly()`
Install it with: `devtools::install_github('hadley/ggplot2')`

Some quality indicators

Here we calculate e.g. number of debarcoded events/metal, median levels of highest signal and second highest signal

for (i in seq_along(res)){
  
  dat = dats_agg[[i]]
  re = res[[i]]
  
  name = names(dats_agg)[i]
  tdat = dat %>%
    mutate(bcid = bc_ids(re)) %>%
    filter(bcid != '0') %>%
    dplyr::select(-c(Start_push, End_push, Pushes_duration,   X , Y  ,Z)) %>%
  melt.data.table(id.vars = c('metal', 'mass','file', 'bcid')) %>%
  do(data.table(.)[, list(med=median(value), n=.N), by=.(variable, metal, mass, bcid,file)]) 
  
  
  # find the highest metal, second highest metal
  sumdat = tdat[ , .(
    highestvariable = variable[med == max(med)],
    highestmed = max(med),
    secondhighestvariable = variable[med == sort(med,partial=length(med)-1)[length(med)-1]],
    secondhighestmed = sort(med,partial=length(med)-1)[length(med)-1],
    n=max(n)
  )  ,by=.( mass, bcid,file)]
  
  print(sumdat)
}
res_uncor = lapply(dats_agg, function(x) re_from_dat(x,
                                               ss_ms=x[!is.na(mass), unique(mass)],
                                               minevents = 40,
                                              correct_bc = NULL ))
Debarcoding data...
 o ordering
 o classifying events
Normalizing...
Computing deltas...
Computing counts and yields...
NaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedDebarcoding data...
 o ordering
 o classifying events
Normalizing...
Computing deltas...
Computing counts and yields...
NaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs producedNaNs produced
sms_uncor = lapply(res_uncor, function(x) computeSpillmat(x))

Assure that the results are exactly the same when ensuring that now debarcoding error happened by using the annotation from the file names:

ndig = 8
for (i in seq_along(sms)){
print('all equal?')
print(all(round(sms_uncor[[i]], digits=ndig) == round(sms[[i]],digits = ndig)))
#diffmat = abs(round(sms_uncor[[i]], digits=ndig)-round(sms[[i]],digits = ndig))/round(sms[[i]],digits = ndig)
#match(T,diffmat > 0.01)
}
[1] "all equal?"
[1] TRUE
[1] "all equal?"
[1] TRUE

-> The results are exactly equal. Thus just debarcoding - without using any information about where the pixels actually belong - seems to be a vaild option to estimate the spillover.

The plot below reproduces plots to check the linearity of spillover

Define a helper function

plot_binplot <- function(imgs, fn, x_var, y_var, perc=0.99, nbins=100, fkt=median){
    # This function makes a 'quantile' binning, binning the data in nbins that contain an equal number of events.
    dat = copy(imgs[[fn]])
    print(dat)
    #dat[, bins:= cut(get(x_var), seq(0, quantile(get(x_var),perc),length.out = nbins), right=T, include.lowest = T)]
    dat = subset(dat, get(x_var) < quantile(get(x_var),perc))
    dat[, bins:=  ntile(get(x_var), nbins)]
    x = melt.data.table(dat, id.vars = 'bins')
    x = x[, .(binmean=fkt(value)), by=.(bins, variable)]
    x = dcast.data.table(x[!is.na(bins),], 'bins~variable', value.var='binmean')
    
    ggplot(x, aes(x=get(x_var), y=get(y_var))) +
        geom_smooth(method = 'lm', alpha =0.5)+
        geom_point()+
        xlab(x_var) +
        ylab(y_var)+
        expand_limits(x=0, y=0)+
           stat_poly_eq(formula=as.formula('y~x'), aes(label = paste(..eq.label.., ..rr.label.., sep = "~~~")), 
                parse = TRUE) +  
        theme(aspect.ratio=1)
    
}

Plot the spillover relationships

fn = "Er166_27_Er166_28.txt"
x_var = "Er166Di"
y_var= "Er167Di"
p = plot_binplot(pltimgs, fn, x_var, y_var, perc=0.95, nbins=20, fkt = median)
'measure.vars' [Start_push, End_push, Pushes_duration, X, ...] are not all of the same type. By order of hierarchy, the molten data value column will be of type 'double'. All measure variables not of type 'double' will be coerced to. Check DETAILS in ?melt.data.table for more on coercion.
p= p+ggtitle('Fig4 A upper')
print(p)

fn ="Er166_27_Er166_28.txt"
x_var = "Er166Di"
y_var= "Er168Di"
pltimgs=list_img_ss[[1]]
p = plot_binplot(pltimgs, fn, x_var, y_var, perc=0.9, nbins=25, fkt = median)
'measure.vars' [Start_push, End_push, Pushes_duration, X, ...] are not all of the same type. By order of hierarchy, the molten data value column will be of type 'double'. All measure variables not of type 'double' will be coerced to. Check DETAILS in ?melt.data.table for more on coercion.
p= p+ggtitle('Fig4 A lower')
print(p)

-> This reproduces Fig 4A

LS0tCnRpdGxlOiAiU3BpbGxvdmVyIGVzdGltYXRpb24gSU1DIgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgojIEFpbQpUaGlzIHNjcmlwdCBzaG93cyBob3cgdG8gZXN0aW1hdGUgc3BpbGxvdmVyIGZyb20gc2luZ2xlIG1ldGFsIHNwb3RzIG9uIGFuIGFnYXJvc2UgY29hdGVkIHNsaWRlLgpFYWNoIHNwb3Qgc2hvdWxkIGJlIGltYWdlZCB3aXRoIGEgc2luZ2xlIGFjcXVpc2l0aW9uLiBUaGUgbmFtZSBvZiB0aGUgYWNxdWlzaXRpb24gc2hvdWxkIGJlIHRoZSBtZXRhbCB0aGF0IGlzIHVzZWQ6CkUuZy4gUGFub3JtYUFfMV9ZYjE3Nl8yMy50eHQKCldoZW4gcnVuIHdpdGggdGhlIGV4YW1wbGUgZGF0YSBpdCByZXByb2R1Y2VzIHRoZSBzcGlsbG92ZXIgZXN0aW1hdGlvbiBzaG93biBpbiBGaWcgUzVBIGFzIHdlbGwgYXMgRmlnIDRBCgojIFNjcmlwdAojIyBsb2FkIGFsbCBsaWJyYXJpZXMKYGBge3IgTGlicmFyaWVzLCBtZXNzYWdlPUZBTFNFfQpsaWJyYXJ5KENBVEFMWVNUKQpsaWJyYXJ5KGRhdGEudGFibGUpCmxpYnJhcnkoZ2dwbG90MikKbGlicmFyeShmbG93Q29yZSkKbGlicmFyeShkcGx5cikKbGlicmFyeShkdHBseXIpCmxpYnJhcnkoc3RyaW5ncikKbGlicmFyeShnZ3BtaXNjKQoKc291cmNlKCdzcGlsbG92ZXJfaW1jX2hlbHBlcnMuUicpCmBgYAoKCiMjIHNldHVwIHRoZSBjb25maWd1cmF0aW9uIHZhcmlhYmxlcwpgYGB7ciBTZXR1cH0KIyBsaXN0IG9mIGZvbGRlcnMgdGhhdCBjb250YWluIGVhY2ggYSBjb21wbGV0ZSBzaW5nbGUgc3RhaW4gYWNxdWlzaXRpb24gKGUuZy4gaW4gY2FzZSB0aGF0IG9uZSB3YW50cyB0byBydW4gYW5kIGNvbXBhcmUgbXVsdGlwbGUgc2luZ2xlIHN0YWlucyBmcm9tIGRpZmZlcmVudCBkYXlzKQpmb2xzX3NzID0gYygnLi4vZGF0YS9GaWd1cmVfUzUvU3BpbGxvdmVyX01hdHJpeF8yJywnLi4vZGF0YS9GaWd1cmVfUzUvU3BpbGxvdmVyX01hdHJpeF8xJyApCgojIG91dHB1dCBmb2xkZXIKZm9sX291dCA9ICcuLi9kYXRhL0ZpZ3VyZV9TNS8nCiMgbmFtZSBwcmVmaXggZm9yIGFsbCBvdXRwdXQKcHJlZml4ID0gcGFzdGUwKFN5cy5EYXRlKCksICdfdjFfJykKYGBgCgoKIyMgbG9hZCBzaW5nbGUgc3RhaW5zCiMjIyBEYXRhIGxvYWRpbmcKYGBge3J9CiMgbG9hZCB0aGUgZGF0YQpsaXN0X2ltZ19zcyA8LWxhcHBseShmb2xzX3NzLCBsb2FkX3NzX2ZvbCkKbmFtZXMobGlzdF9pbWdfc3MpIDwtIGZvbHNfc3MKYGBgCgojIyMgQWRhcHQgdGhlIGNvbHVtbiBuYW1lcyB0byBiZSByZWNvZ25pemVkIG1ldGFsIG5hbWVzIGJ5IENBVEFMWVNUIApDQVRBTFlTVCBuZWVkcyB0byBoYXZlIHRoZSBtZXRhbCBuYW1lcyBpbiB0aGUgZm9ybWF0IChNRVRBTCkoTUFTUylEaQpgYGB7cn0KbGlzdF9pbWdfc3MgPSBsYXBwbHkobGlzdF9pbWdfc3MsIGZ1bmN0aW9uKHgpIGxhcHBseSh4LCBmaXhuYW1lcykpCmRhdHNfcmF3ID0gbGFwcGx5KGxpc3RfaW1nX3NzLCBpbWdsaXN0MmRhdCkKYGBgCgoKIyMjIEV4dHJhY3QgdGhlIHNpbmdsZSBzdGFpbiBtYXNzZXMgZnJvbSB0aGUgYWNxdWlzaXRpb24gbmFtZQpUaGlzIG5lZWRzIHRvIGJlIGNoYW5nZWQgaW4gY2FzZSBhIGRpZmZlcmVudCBuYW1pbmcgc2NoZW1lIGlzIHVzZWQhCmBgYHtyIEdldCBiYyBtYXNzZXN9CmZvciAoZGF0IGluIGRhdHNfcmF3KXsKICBkYXRbLCBtZXRhbDo9IHN0cnNwbGl0KC5CWVtbMV1dLCAnXycpW1sxXV1bM10sYnk9ZmlsZV0KICBkYXRbLCBtYXNzOj0gYXMubnVtZXJpYyhzdHJfZXh0cmFjdF9hbGwoLkJZW1sxXV0sICJbMC05XSsiKVtbMV1dKSxieT1tZXRhbF0KfQpgYGAKCiMjIFZpc3VhbGl6YXRpb24gb2YgdGhlIHJhdyBkYXRhCkluIHRoZSBmb2xsb3dpbmcgc2VjdGlvbiB0aGUgcmF3IGRhdGEgaXMgdmlzdWFsaXplZAoKIyMjIENhbGN1bGF0ZSBwZXItZmlsZSBtZWRpYW5zCmBgYHtyfQpkYXRzX3Jhd19zdW0gPSByYmluZGxpc3QobGFwcGx5KGRhdHNfcmF3LCBjYWxjX2ZpbGVfbWVkaWFucyksaWRjb2wgPSBUKQpgYGAKCgojIyMgVmlzdWFsaXplIHBlci1maWxlIG1lZGlhbnMKUGxvdHMgdGhlIG1lZGlhbiBvZiB0aGUgZGF0YS4gSXQgaXMgcmVjb21tZW5kZWQgdG8gaGF2ZSA+MjAwIGNvdW50cyBmb3IgYWxsIHRoZSBjaGFubmVscy4KVGhpcyBpcyBhbHNvIGEgZ29vZCBwbG90IHRvIGNoZWNrIGlmIHRoZSBtZXRhbCBzcG90cyByZWFsbHkgY29udGFpbiB0aGUgY29ycmVjdCBtZXRhbCEKYGBge3IgZmlnLmhlaWdodD0xMywgZmlnLndpZHRoPTIwfQpkYXRzX3Jhd19zdW0gJT4lCiAgZ2dwbG90KGFlcyh4PW1hc3MsIHk9bWVkLCBjb2xvcj0uaWQpKSsKICBmYWNldF93cmFwKH5maWxlK21ldGFsLCBzY2FsZXMgPSAnZnJlZV95JykrCiAgZ2VvbV9sYWJlbChhZXMobGFiZWw9dmFyaWFibGUpLCBzaXplPTQpCmBgYAoKCgojIyMgIE9wdGlvbmFsIGRhdGEgYmluaW5nCgpJZiB0aGUgbWVkaWFuIHBlci1waXhlbCBpbnRlbnNpdGllcyBhcmUgdG8gbG93LCBpdCBjb3VsZCBiZSB3b3J0aCB0byBzdW0gdXAgc29tZSBjb25zZWN1dGVpdmUgcGl4ZWxzIHRvIGdldCBhIGJldHRlciBhY2N1cmFjeSBmb3IgdGhlIGVzdGltYXRpb24KKGhlcmUgbm90IHRoZSBjYXNlKS4gVGhpcyBpcyB2YWxpZCBiZWNhdXNlIGZvciBzZWdtZW50YXRpb24gYmFzZWQgcXVhbnRpdGF0aXZlIGltYWdlIGFuYWx5c2lzIHVzdWFsbHkgYW55d2F5cyBwaXhlbHMgYXJlIGFnZ3JlZ2F0ZWQuIElmIHRoZSBiaW5uaW5nIGlzIGNob29zZW4gdG8gYmlnLCB0aGVyZSBpcyBob3dldmVyIGEgcG90ZW50aWFsIGFjY3VtdWxhdGlvbiBvZiBiYWNrZ3JvdW5kIG5vaXNlLgoKYGBge3J9CiMgZGVmaW5lcyBvdmVyIGhvdyBtYW55IHBpeGVscyB0aGUgYWdncmVnYXRpb24gc2hvdWxkIGhhcHBlbgojIDEgPSBubyBhZ2dyZWdhdGlvbgpucGl4ZWxiaW4gPSAxCgpkYXRzX2FnZyA8LSBsYXBwbHkoZGF0c19yYXcsIGZ1bmN0aW9uKHgpIGFnZ3JlZ2F0ZV9waXhlbHMoeCwgbj1ucGl4ZWxiaW4pKQpkYXRzX2FnZ19zdW0gPSByYmluZGxpc3QobGFwcGx5KGRhdHNfYWdnLCBjYWxjX2ZpbGVfbWVkaWFucyksIGlkY29sID0gVCkKYGBgCgoKIyMjIFZpc3VhbGl6ZSBwZXItZmlsZSBtZWRpYW5zIGFmdGVyIGJpbm5pbmcKVGhlIGludGVuc2l0aWVzIGluY3JlYXNlIGFjY29yZGluZyB0byB0aGUgYWdncmVnYXRpb24gZmFjdG9yCmBgYHtyIGZpZy53aWR0aD0xNywgZmlnLmhlaWdodD0xMH0KZGF0c19hZ2dfc3VtICU+JQogIGdncGxvdChhZXMoeD1tYXNzLCB5PW1lZCwgY29sb3I9LmlkKSkrCiAgZmFjZXRfd3JhcCh+ZmlsZSttZXRhbCwgc2NhbGVzID0gJ2ZyZWVfeScpKwogIGdlb21fbGFiZWwoYWVzKGxhYmVsPXZhcmlhYmxlKSkKCmBgYAoKIyMgQ0FUQUxZU1QgYmFzZWQgY29tcGVuc2F0aW9uCgojIyMgRGVmaW5pdGlvbiBvZiBzb21lIGhlbHBlciBmdW5jdGlvbnMKYGBge3IgRGVmaW5lIGhlbHBlciBmdW5jdGlvbnN9CgpgYGAKCiMjIGVzdGltYXRlIHRoZSBzcGlsbG92ZXIKVG8gZXN0aW1hdGUgdGhlIHNwaWxsb3ZlciwgdGhlIChhZ2dyZWdhdGVkKSBwaXhlbCB2YWx1ZXMgYXJlIGZpcnN0IGRlYmFyY29kZWQgdXNpbmcgQ0FUQUxZU1QsIHRyZWF0aW5nIHRoZW0gbGlrZSBzaW5nbGUgY2VsbHMuIFRoaXMgc3RlcCBhY3RzIGFzIGEgcXVhbGl0eSBmaWx0ZXIgdG8gcmVtb3ZlIGJhY2tncm91bmQvbm9pc3kvd2VhayBwaXhlbHMgYXMgd2VsbCBhcyBwaXhlbHMgd2l0aCBhcnRlZmFjdHMgKGUuZy4gc3BlY2xlcyB3aXRoIHN0cm9uZyBzaWduYWwgaW4gbWFueSBjaGFubmVscykuCklmIHRoZSB0cnVlIG1ldGFsIHdhcyBjb3JyZWN0bHkgZW5jb2RlZCBpbiB0aGUgZmlsZW5hbWUsIHRoZSAncmVtb3ZlX2luY29ycmVjdF9iYycgb3B0aW9uIHdpbGwgY2hlY2sgdGhlIGRlYmFyY29kaW5nIGFuZCByZW1vdmUgZXZlbnRzIGFzc2lnbmVkIHRvIHRoZSB3cm9uZyBiYXJjb2RlLgoKVGhlbiB0aGlzIGlkZW50aWZpZWQsIHN0cm9uZyBzaW5nbGUgc3RhaW4gcGl4ZWxzIHdpbGwgYmUgdXNlZCBmb3IgdGhlIHNwaWxsb3ZlciBlc3RpbWF0aW9uLgoKYGBge3IgQmlubmVkfQpyZXMgPSBsYXBwbHkoZGF0c19hZ2csIGZ1bmN0aW9uKHgpIHJlX2Zyb21fZGF0KHgsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc3NfbXM9eFshaXMubmEobWFzcyksIHVuaXF1ZShtYXNzKV0sCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWluZXZlbnRzID0gNDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjb3JyZWN0X2JjID0geFsgLCB1bmlxdWUobWFzcyldKSkKc21zID0gbGFwcGx5KHJlcywgZnVuY3Rpb24oeCkgY29tcHV0ZVNwaWxsbWF0KHgpKQoKCmBgYAoKIyMjIHNhdmUgdGhlIHNwaWxsb3ZlciBtYXRyaWNlcwoKYGBge3J9CmZvciAoaSBpbiBzZXFfYWxvbmcoc21zKSl7CiAgb3V0bmFtZSA9IGZpbGUucGF0aChmb2xfb3V0LCBwYXN0ZTAocHJlZml4LCBiYXNlbmFtZShmb2xzX3NzW2ldKSwnX3NtLmNzdicpKQogIHdyaXRlLmNzdihzbXNbW2ldXSxmaWxlID0gb3V0bmFtZSkKfQpgYGAKCgojIyMgVmlzdWFsaXphdGlvbiBvZiB0aGUgc3BpbGxvdmVyIG1hdHJpeAoKYGBge3J9CmZvciAoaSBpbiBzZXFfYWxvbmcoc21zKSl7CiAgcHJpbnQobmFtZXMoZGF0c19hZ2cpW2ldKQogIHNzX21zID0gZGF0c19hZ2dbW2ldXVshaXMubmEobWFzcyksIHVuaXF1ZShtYXNzKV0KICBwID0gQ0FUQUxZU1Q6OnBsb3RTcGlsbG1hdChzc19tcyxzbXNbW2ldXSkKICBwcmludChwKQp9CmBgYAoKCiMjIyBTb21lIHF1YWxpdHkgaW5kaWNhdG9ycwoKSGVyZSB3ZSBjYWxjdWxhdGUgZS5nLiBudW1iZXIgb2YgZGViYXJjb2RlZCBldmVudHMvbWV0YWwsIG1lZGlhbiBsZXZlbHMgb2YgaGlnaGVzdCBzaWduYWwgYW5kIHNlY29uZCBoaWdoZXN0IHNpZ25hbAoKYGBge3J9Cgpmb3IgKGkgaW4gc2VxX2Fsb25nKHJlcykpewogIAogIGRhdCA9IGRhdHNfYWdnW1tpXV0KICByZSA9IHJlc1tbaV1dCiAgCiAgbmFtZSA9IG5hbWVzKGRhdHNfYWdnKVtpXQogIHRkYXQgPSBkYXQgJT4lCiAgICBtdXRhdGUoYmNpZCA9IGJjX2lkcyhyZSkpICU+JQogICAgZmlsdGVyKGJjaWQgIT0gJzAnKSAlPiUKICAgIGRwbHlyOjpzZWxlY3QoLWMoU3RhcnRfcHVzaCwgRW5kX3B1c2gsIFB1c2hlc19kdXJhdGlvbiwgICBYICwgWSAgLFopKSAlPiUKICBtZWx0LmRhdGEudGFibGUoaWQudmFycyA9IGMoJ21ldGFsJywgJ21hc3MnLCdmaWxlJywgJ2JjaWQnKSkgJT4lCiAgZG8oZGF0YS50YWJsZSguKVssIGxpc3QobWVkPW1lZGlhbih2YWx1ZSksIG49Lk4pLCBieT0uKHZhcmlhYmxlLCBtZXRhbCwgbWFzcywgYmNpZCxmaWxlKV0pIAogIAogIAogICMgZmluZCB0aGUgaGlnaGVzdCBtZXRhbCwgc2Vjb25kIGhpZ2hlc3QgbWV0YWwKICBzdW1kYXQgPSB0ZGF0WyAsIC4oCiAgICBoaWdoZXN0dmFyaWFibGUgPSB2YXJpYWJsZVttZWQgPT0gbWF4KG1lZCldLAogICAgaGlnaGVzdG1lZCA9IG1heChtZWQpLAogICAgc2Vjb25kaGlnaGVzdHZhcmlhYmxlID0gdmFyaWFibGVbbWVkID09IHNvcnQobWVkLHBhcnRpYWw9bGVuZ3RoKG1lZCktMSlbbGVuZ3RoKG1lZCktMV1dLAogICAgc2Vjb25kaGlnaGVzdG1lZCA9IHNvcnQobWVkLHBhcnRpYWw9bGVuZ3RoKG1lZCktMSlbbGVuZ3RoKG1lZCktMV0sCiAgICBuPW1heChuKQogICkgICxieT0uKCBtYXNzLCBiY2lkLGZpbGUpXQogIAogIHByaW50KHN1bWRhdCkKfQoKYGBgCgoKCmBgYHtyIEJpbm5lZCB1bmNvcn0KcmVzX3VuY29yID0gbGFwcGx5KGRhdHNfYWdnLCBmdW5jdGlvbih4KSByZV9mcm9tX2RhdCh4LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNzX21zPXhbIWlzLm5hKG1hc3MpLCB1bmlxdWUobWFzcyldLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbmV2ZW50cyA9IDQwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29ycmVjdF9iYyA9IE5VTEwgKSkKc21zX3VuY29yID0gbGFwcGx5KHJlc191bmNvciwgZnVuY3Rpb24oeCkgY29tcHV0ZVNwaWxsbWF0KHgpKQoKCmBgYAoKQXNzdXJlIHRoYXQgdGhlIHJlc3VsdHMgYXJlIGV4YWN0bHkgdGhlIHNhbWUgd2hlbiBlbnN1cmluZyB0aGF0IG5vdyBkZWJhcmNvZGluZyBlcnJvciBoYXBwZW5lZCBieSB1c2luZyB0aGUgYW5ub3RhdGlvbiBmcm9tIHRoZSBmaWxlIG5hbWVzOgoKYGBge3J9Cm5kaWcgPSA4CmZvciAoaSBpbiBzZXFfYWxvbmcoc21zKSl7CnByaW50KCdhbGwgZXF1YWw/JykKcHJpbnQoYWxsKHJvdW5kKHNtc191bmNvcltbaV1dLCBkaWdpdHM9bmRpZykgPT0gcm91bmQoc21zW1tpXV0sZGlnaXRzID0gbmRpZykpKQojZGlmZm1hdCA9IGFicyhyb3VuZChzbXNfdW5jb3JbW2ldXSwgZGlnaXRzPW5kaWcpLXJvdW5kKHNtc1tbaV1dLGRpZ2l0cyA9IG5kaWcpKS9yb3VuZChzbXNbW2ldXSxkaWdpdHMgPSBuZGlnKQojbWF0Y2goVCxkaWZmbWF0ID4gMC4wMSkKfQpgYGAKLT4gVGhlIHJlc3VsdHMgYXJlIGV4YWN0bHkgZXF1YWwuIFRodXMganVzdCBkZWJhcmNvZGluZyAtIHdpdGhvdXQgdXNpbmcgYW55IGluZm9ybWF0aW9uIGFib3V0IHdoZXJlIHRoZSBwaXhlbHMgYWN0dWFsbHkgYmVsb25nIC0gc2VlbXMgdG8gYmUgYSB2YWlsZCBvcHRpb24gdG8gZXN0aW1hdGUgdGhlIHNwaWxsb3Zlci4KCgojIyBUaGUgcGxvdCBiZWxvdyByZXByb2R1Y2VzIHBsb3RzIHRvIGNoZWNrIHRoZSBsaW5lYXJpdHkgb2Ygc3BpbGxvdmVyCgojIyMgRGVmaW5lIGEgaGVscGVyIGZ1bmN0aW9uCgpgYGB7cn0KcGxvdF9iaW5wbG90IDwtIGZ1bmN0aW9uKGltZ3MsIGZuLCB4X3ZhciwgeV92YXIsIHBlcmM9MC45OSwgbmJpbnM9MTAwLCBma3Q9bWVkaWFuKXsKICAgICMgVGhpcyBmdW5jdGlvbiBtYWtlcyBhICdxdWFudGlsZScgYmlubmluZywgYmlubmluZyB0aGUgZGF0YSBpbiBuYmlucyB0aGF0IGNvbnRhaW4gYW4gZXF1YWwgbnVtYmVyIG9mIGV2ZW50cy4KICAgIGRhdCA9IGNvcHkoaW1nc1tbZm5dXSkKICAgIHByaW50KGRhdCkKICAgICNkYXRbLCBiaW5zOj0gY3V0KGdldCh4X3ZhciksIHNlcSgwLCBxdWFudGlsZShnZXQoeF92YXIpLHBlcmMpLGxlbmd0aC5vdXQgPSBuYmlucyksIHJpZ2h0PVQsIGluY2x1ZGUubG93ZXN0ID0gVCldCiAgICBkYXQgPSBzdWJzZXQoZGF0LCBnZXQoeF92YXIpIDwgcXVhbnRpbGUoZ2V0KHhfdmFyKSxwZXJjKSkKICAgIGRhdFssIGJpbnM6PSAgbnRpbGUoZ2V0KHhfdmFyKSwgbmJpbnMpXQogICAgeCA9IG1lbHQuZGF0YS50YWJsZShkYXQsIGlkLnZhcnMgPSAnYmlucycpCiAgICB4ID0geFssIC4oYmlubWVhbj1ma3QodmFsdWUpKSwgYnk9LihiaW5zLCB2YXJpYWJsZSldCiAgICB4ID0gZGNhc3QuZGF0YS50YWJsZSh4WyFpcy5uYShiaW5zKSxdLCAnYmluc352YXJpYWJsZScsIHZhbHVlLnZhcj0nYmlubWVhbicpCiAgICAKICAgIGdncGxvdCh4LCBhZXMoeD1nZXQoeF92YXIpLCB5PWdldCh5X3ZhcikpKSArCiAgICAgICAgZ2VvbV9zbW9vdGgobWV0aG9kID0gJ2xtJywgYWxwaGEgPTAuNSkrCiAgICAgICAgZ2VvbV9wb2ludCgpKwogICAgICAgIHhsYWIoeF92YXIpICsKICAgICAgICB5bGFiKHlfdmFyKSsKICAgICAgICBleHBhbmRfbGltaXRzKHg9MCwgeT0wKSsKICAgICAgICAgICBzdGF0X3BvbHlfZXEoZm9ybXVsYT1hcy5mb3JtdWxhKCd5fngnKSwgYWVzKGxhYmVsID0gcGFzdGUoLi5lcS5sYWJlbC4uLCAuLnJyLmxhYmVsLi4sIHNlcCA9ICJ+fn4iKSksIAogICAgICAgICAgICAgICAgcGFyc2UgPSBUUlVFKSArICAKICAgICAgICB0aGVtZShhc3BlY3QucmF0aW89MSkKICAgIAp9CmBgYApQbG90IHRoZSBzcGlsbG92ZXIgcmVsYXRpb25zaGlwcwpgYGB7cn0KCgpmbiA9ICJFcjE2Nl8yN19FcjE2Nl8yOC50eHQiCnhfdmFyID0gIkVyMTY2RGkiCnlfdmFyPSAiRXIxNjdEaSIKcCA9IHBsb3RfYmlucGxvdChwbHRpbWdzLCBmbiwgeF92YXIsIHlfdmFyLCBwZXJjPTAuOTUsIG5iaW5zPTIwLCBma3QgPSBtZWRpYW4pCnA9IHArZ2d0aXRsZSgnRmlnNCBBIHVwcGVyJykKcHJpbnQocCkKCgpmbiA9IkVyMTY2XzI3X0VyMTY2XzI4LnR4dCIKeF92YXIgPSAiRXIxNjZEaSIKeV92YXI9ICJFcjE2OERpIgpwbHRpbWdzPWxpc3RfaW1nX3NzW1sxXV0KcCA9IHBsb3RfYmlucGxvdChwbHRpbWdzLCBmbiwgeF92YXIsIHlfdmFyLCBwZXJjPTAuOSwgbmJpbnM9MjUsIGZrdCA9IG1lZGlhbikKcD0gcCtnZ3RpdGxlKCdGaWc0IEEgbG93ZXInKQpwcmludChwKQoKYGBgCi0+IFRoaXMgcmVwcm9kdWNlcyBGaWcgNEEK